package leetcode

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
func flatten(root *TreeNode) {
	for root != nil {
		left, right := root.Left, root.Right
		root.Left = nil
		if left != nil {
			root.Right = left
			for left.Right != nil {
				left = left.Right
			}
			left.Right = right
		}
		root = root.Right
	}
}

// solution by iterated.
func traversal(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	left := traversal(root.Left)
	right := traversal(root.Right)
	root.Left = nil
	if left != nil {
		root.Right = left
		for left.Right != nil {
			left = left.Right
		}
		left.Right = right
	}
	return root
}
